package com.example.question.tree.tree3;

import com.example.question.tree.tree1.TreeNode;

/**
 * @Date 2023-07-14
 * @Author Jonathan
 */
public class Code10_98 {
    public static void main(String[] args) {

    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return process(root).valid;

    }

    private Helper process(TreeNode node) {
        if (node == null) {
            return null;
        }
        Helper left = process(node.left);
        Helper right = process(node.right);
        //
        if (left == null && right == null) {
            return new Helper(node.val, node.val, true);
        }
        if (left == null) {
            return new Helper(right.max, Math.min(node.val, right.min), right.valid && right.min > node.val);
        }
        if (right == null) {
            return new Helper(node.val, left.min, left.valid && left.max < node.val);
        }

        return new Helper(Math.max(left.max, right.max), Math.min(left.min, right.min), left.valid && right.valid && left.max < node.val && node.val < right.min);
    }

    static class Helper {
        int max;
        int min;
        boolean valid;

        public Helper(int max, int min, boolean valid) {
            this.max = max;
            this.min = min;
            this.valid = valid;
        }
    }
}
